#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

//int cmp(const void* x1, const void* x2)
//{
//    return *(int*)x1 - *(int*)x2;
//}
//
//int threeSumClosest(int* nums, int numsSize, int target) {
//    qsort(nums, numsSize, sizeof(int), cmp);
//    int a = 0;
//    int b = a + 1;
//    int c = numsSize - 1;
//    int max = nums[a] + nums[b] + nums[c];
//    int ret = nums[a] + nums[b] + nums[c];
//    while (a + 1 < c)
//    {
//        b = a + 1;
//        c = numsSize - 1;
//        while (b < c)
//        {
//            max = nums[a] + nums[b] + nums[c];
//            if (abs(ret - target) > abs(max - target))
//            {
//                ret = max;
//            }
//            if (max > target)
//            {
//                c--;
//            }
//            else if (max < target)
//            {
//                b++;
//            }
//            else
//            {
//                return target;
//            }
//        }
//        a++;
//    }
//    return ret;
//}
//
//int main()
//{
//    int arr[] = { 4,0,5,-5,3,3,0,-4,-5 };
//    int numSize = sizeof(arr) / sizeof(arr[0]);
//    int c = threeSumClosest(arr, numSize, -2);
//    printf("%d\n", c);
//	return 0;
//}

//int cmp(const void* x1, const void* x2)
//{
//    return *(int*)x1 - *(int*)x2;
//}
//
//int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
//    qsort(nums, numsSize, sizeof(int), cmp);
//    int n = 0;
//    int i = 0;
//    int a = 0;
//    int b = a + 1;
//    int c = numsSize - 1;
//    while (a + 1 < c)
//    {
//        c = numsSize - 1;
//        b = a + 1;
//        while (b < c)
//        {
//            int sum = nums[a] + nums[b] + nums[c];
//            if (sum > 0)
//            {
//                c--;
//            }
//            else if (sum < 0)
//            {
//                b++;
//            }
//            else
//            {
//                i++;
//                returnColumnSizes = (int**)realloc(returnColumnSizes, sizeof(int) * 3 * i);
//                returnColumnSizes[n][0] = nums[a];
//                returnColumnSizes[n][1] = nums[b];
//                returnColumnSizes[n][2] = nums[c];
//                n++;
//            }
//        }
//        a++;
//    }
//    returnSize = i;
//    return returnColumnSizes;
//}

//char** letterCombinations(char* digits, int* returnSize) {
//    if (digits == NULL)
//    {
//        return NULL;
//    }
//    int i = 0;
//    while (digits[i])
//    {
//        i++;
//    }
//    int num = 1;
//    int n = 0;
//    for (n = 0; n < i; n++)
//    {
//        if (digits[n] == 7 || digits[n] == 9)
//        {
//            num *= 4;
//        }
//        else
//        {
//            num *= 3;
//        }
//    }
//    char** ret = (char**)realloc(ret, sizeof(char*) * num);
//    for (n = 0; n < num; n++)
//    {
//        ret[n] = (char*)calloc(sizeof(char) * 5);
//    }
//    int m = 0;
//    char a1[] = "abc";
//    char a2[] = "def";
//    char a3[] = "ghi";
//    char a4[] = "jkl";
//    char a5[] = "mno";
//    char a6[] = "pqrs";
//    char a7[] = "tuv";
//    char a8[] = "wxyz";
//    for (n = 0; n < i; n++)
//    {
//        for (m = 0; m < num; m++)
//        {
//            if (digits[n] == '2')
//            {
//                if (m < num / 3)
//                {
//                    ret[n][m] = a1[0];
//                }
//                else if (m > num / 3 && m < (num / 3) * 2)
//                {
//                    ret[n][m] = a1[1];
//                }
//                else
//                {
//                    ret[n][m] = a1[2];
//                }
//
//            }
//            else if (digits[n] == '3')
//            {
//                if (m < num / 3)
//                {
//                    ret[n][m] = a2[0];
//                }
//                else if (m > num / 3 && m < (num / 3) * 2)
//                {
//                    ret[n][m] = a2[1];
//                }
//                else
//                {
//                    ret[n][m] = a2[2];
//                }
//
//            }
//            else if (digits[n] == '4')
//            {
//                if (m < num / 3)
//                {
//                    ret[n][m] = a3[0];
//                }
//                else if (m > num / 3 && m < (num / 3) * 2)
//                {
//                    ret[n][m] = a3[1];
//                }
//                else
//                {
//                    ret[n][m] = a3[2];
//                }
//
//            }
//            else if (digits[n] == '5')
//            {
//                if (m < num / 3)
//                {
//                    ret[n][m] = a4[0];
//                }
//                else if (m > num / 3 && m < (num / 3) * 2)
//                {
//                    ret[n][m] = a4[1];
//                }
//                else
//                {
//                    ret[n][m] = a4[2];
//                }
//
//            }
//            else if (digits[n] == '6')
//            {
//                if (m < num / 3)
//                {
//                    ret[n][m] = a5[0];
//                }
//                else if (m > num / 3 && m < (num / 3) * 2)
//                {
//                    ret[n][m] = a5[1];
//                }
//                else
//                {
//                    ret[n][m] = a5[2];
//                }
//
//            }
//            else if (digits[n] == '7')
//            {
//                if (m < num / 4)
//                {
//                    ret[n][m] = a6[0];
//                }
//                else if (m > num / 4 && m < (num / 4) * 2)
//                {
//                    ret[n][m] = a6[1];
//                }
//                else if ((m > num / 4) * 2 && m < (num / 4) * 3)
//                {
//                    ret[n][m] = a6[2];
//                }
//                else
//                {
//                    ret[n][m] = a6[3];
//                }
//            }
//            else if (digits[n] == '8')
//            {
//                if (m < num / 3)
//                {
//                    ret[n][m] = a7[0];
//                }
//                else if (m > num / 3 && m < (num / 3) * 2)
//                {
//                    ret[n][m] = a7[1];
//                }
//                else
//                {
//                    ret[n][m] = a7[2];
//                }
//            }
//            else if (digits[n] == '9')
//            {
//                if (m < num / 4)
//                {
//                    ret[n][m] = a8[0];
//                }
//                else if (m > num / 4 && m < (num / 4) * 2)
//                {
//                    ret[n][m] = a8[1];
//                }
//                else if ((m > num / 4) * 2 && m < (num / 4) * 3)
//                {
//                    ret[n][m] = a8[2];
//                }
//                else
//                {
//                    ret[n][m] = a8[3];
//                }
//            }
//        }
//    }
//    return ret;
//}